package com.wenhai.liuyubobobo.imooc.sort;

import com.wenhai.liuyubobobo.imooc.heap.MaxHeap;

/**
 * 堆排序
 *
 * @author wenhai
 * @date   2021/3/9
 */
public class HeapSort {
    private HeapSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] data) {
        if (data == null || data.length == 1) {
            return;
        }
        MaxHeap<E> heap = new MaxHeap<>(data.length);
        for (E e : data) {
            heap.add(e);
        }
        for (int i = data.length - 1; i >= 0; i--) {
            data[i] = heap.getMax();
        }
    }

    public static <E extends Comparable<E>> void replaceSort(E[] data) {
        if (data == null || data.length == 1) {
            return;
        }
        for (int i = (data.length - 2) / 2; i >= 0; i--) {
            siftDown(data, i, data.length);
        }
        for (int i = data.length - 1; i > 0; i--) {
            swap(data, 0, i);
            siftDown(data, 0, i);
        }

    }

    private static <E extends Comparable<E>> void siftDown(E[] data, int index, int bound) {
        while (2 * index + 1 < bound) {
            int maxIndex = index * 2 + 1;
            if (maxIndex + 1 < bound && data[maxIndex + 1].compareTo(data[maxIndex]) > 0) {
                maxIndex = maxIndex + 1;
            }
            if (data[index].compareTo(data[maxIndex]) >= 0) {
                break;
            }
            swap(data, index, maxIndex);
            index = maxIndex;
        }

    }


    public static <E extends Comparable<E>> void swap(E[] data, int from, int to) {
        if (from < 0 || to < 0 || from > data.length || to > data.length) {
            throw new IndexOutOfBoundsException("Illegal from index or to index ");
        }
        E temp = data[from];
        data[from] = data[to];
        data[to] = temp;
    }
}
